package leetcode.code1906;

import java.util.ArrayList;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int[] minDifference(int[] nums, int[][] queries) {
		int arraySize = 101;
		List<Integer>[] indexs = new ArrayList[arraySize];
		for (int i = 0; i < arraySize; i++) {
			indexs[i] = new ArrayList<>();
		}
		for (int i = 0; i < nums.length; i++) {
			indexs[nums[i]].add(i);
		}
		int len = queries.length;
		int[] ans = new int[len];
		for (int i = 0; i < len; i++) {
			int l = queries[i][0], r = queries[i][1];
			int last = -1000;
			int min = Integer.MAX_VALUE;
			for (int j = 0; j < 101; j++) {// 这
				if (this.havej(indexs[j], l, r)) {
					min = Math.min(min, j - last);
					last = j;
				}
			}
			ans[i] = min > 100 ? -1 : min;
		}
		return ans;
	}

	private boolean havej(List<Integer> list, int L, int R) {
		int l = 0, r = list.size() - 1;
		int ans = -1;
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			if (list.get(mid) >= L) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		if (ans == -1) {
			return false;
		}
		int index = list.get(ans);
		return index <= R;
	}

	private List<Integer>[] group(int[] nums) {
		int arraySize = 101;
		List<Integer>[] indexs = new ArrayList[arraySize];
		for (int i = 0; i < arraySize; i++) {
			indexs[i] = new ArrayList<>();
		}
		for (int i = 0; i < nums.length; i++) {
			indexs[nums[i]].add(i);
		}
		return indexs;
	}

	@Override
	public void debug4() {
		H.compare(H.str2array3("[2,1,4,1]"),
				this.minDifference(H.str2array3("[1,3,4,8]"), H.str2array1("[[0,1],[1,2],[2,3],[0,3]]")));
		H.compare(H.str2array3("[-1,1,1,3]"),
				this.minDifference(H.str2array3("[4,5,2,2,7,10]"), H.str2array1("[[2,3],[0,2],[0,5],[3,5]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
